---

Scalability of a parallel arbitrary-dimensional image distance transform

 

Scott Pardue, Nikos Chrisochoides and Andrey Chernikov.

 

Published in VMASC 2014 Capstone Conference, Suffolk, VA, April, 2014

 

Abstract

 

Computing the Euclidean Distance Transform (EDT) for binary images is an important problem with applications involving medical image processing, computer vision, computational geometry, and pattern recognition. Currently, there exists a sequential algorithm of O(n) complexity developed by Maurer et al. and a parallel implementation of Maurer's algorithm developed by Staubs et al. with a theoretical complexity of O(n/p) for n voxels and p threads. In this paper, we present an efficient, scalable parallel implementation of Maurer's algorithm for large datasets with high efficiency for 16 processors.